public class MinPathSum {

    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[m - 1][n - 1] = grid[m - 1][n -1];
        for (int i = m - 1; i >= 0 ; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (i == m - 1 && j == n - 1) continue;
                int a = Integer.MAX_VALUE;
                int b = Integer.MAX_VALUE;
                if (i < m - 1) {
                    a = dp[i + 1][j];
                }
                if (j < n - 1) {
                    b = dp[i][j + 1];
                }
                dp[i][j] = grid[i][j] + Math.min(a, b);
            }
        }
        return dp[0][0];
    }
}
